/*
 * @lc app=leetcode.cn id=1206 lang=cpp
 * @lcpr version=30204
 *
 * [1206] 设计跳表
 */

// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <time.h>
// @lcpr-template-end
// @lc code=start
struct SkiplistNode
{
    int _val;
    vector<SkiplistNode*> _nextV;

    SkiplistNode(int val, int level)
        : _val(val), _nextV(level, nullptr)
    {
    }
};

class Skiplist
{
    typedef SkiplistNode Node;

public:
    Skiplist()
    {
        srand(time(0));
        _head = new Node(-1, 1);
    }

    bool search(int target)
    {
        Node* cur = _head;
        int level = _head->_nextV.size() - 1;
        while (level >= 0)
        {
            // 查找的比下一个值大，向右走
            if (cur->_nextV[level] && cur->_nextV[level]->_val < target)
            {
                cur = cur->_nextV[level];
            }
            // 下一个为空 或者 比查找的值小，向下走
            else if (cur->_nextV[level] == nullptr || cur->_nextV[level]->_val > target)
            {
                --level;
            }
            else
            {
                return true;
            }
        }
        return false;
    }

    vector<Node*> FindPrevNode(int num)
    {
        vector<Node*> prevV(_maxLevel + 1, _head);
        Node* cur = _head;          // 当前遍历到的节点，从头部开始
        int level = _head->_nextV.size() - 1;   // 起始查找层：跳表当前的最高层
        while (level >= 0)  // 遍历完所有层（从最高层到第 0 层）
        {
            // 情况1：当前层的下一个节点存在，且值 < num → 继续向右找（目标在右侧）
            if (cur->_nextV[level] && cur->_nextV[level]->_val < num)
            {
                cur = cur->_nextV[level];
            }
            // 情况2：当前层的下一个节点不存在，或值 ≥ num → 此节点是当前层的前驱
            else if (cur->_nextV[level] == nullptr || cur->_nextV[level]->_val >= num)
            {
                prevV[level] = cur;
                --level;
            }
        }
        return prevV;
    }

    void add(int num)
    {
		vector<Node*> prevV = FindPrevNode(num);
        
        int n = RandomLevel();
        Node* newnode = new Node(num, n);

        if (n > _head->_nextV.size())
        {
            _head->_nextV.resize(n, nullptr);
			prevV.resize(n, _head);
        }

        for (size_t i = 0; i < n; ++i)
        {
            newnode->_nextV[i] = prevV[i]->_nextV[i];
            prevV[i]->_nextV[i] = newnode;
        }
    }

    bool erase(int num)
    {
        if (!search(num))
        {
            return false;
        }
		vector<Node*> prevV = FindPrevNode(num);
		Node* del = prevV[0]->_nextV[0];
		for (size_t i = 0; i < del->_nextV.size(); ++i)
		{
			prevV[i]->_nextV[i] = del->_nextV[i];
		}
        delete del;
        return true;
    }

    int RandomLevel()
    {
        size_t level = 1;
        while (rand() <= RAND_MAX * _p && level < _maxLevel)
        {
            ++level;
        }

        return level;
    }

    void Print()
    {
        for (size_t i = 0; i < _head->_nextV.size(); ++i)
        {
            Node* cur = _head;
            while (cur)
            {
                cout << cur->_val << " -> ";
                cur = cur->_nextV[i];
            }
            cout << endl;
        }
    }

private:
    Node* _head;
    size_t _maxLevel = 32;
    double _p = 0.25;
};

/**
 * Your Skiplist object will be instantiated and called as such:
 * Skiplist* obj = new Skiplist();
 * bool param_1 = obj->search(target);
 * obj->add(num);
 * bool param_3 = obj->erase(num);
 */
// @lc code=end
